The invention relates to a Carry-Select Adder structure comprising a carry generation network and a multiplexer to select particular pre-calculated sums via orthogonal signal levels, plus to a method to generate orthogonal signal levels in such a Carry Select Adder structure.
In elementary arithmetic a carry is a digit that is transferred from one column of digits to another column or more significant digits during a calculation algorithm. When speaking of a digital circuit like an adder structure, the word carry is used in a similar sense. Furthermore when speaking of an adder structure in this document, a binary adder structure is meant.
In most computers, the carry from the Most significant Bit (MSB) of an arithmetic operation is placed in a special carry bit which can be used as a carry-in for multiple precision arithmetic logic circuits or tested and used to control execution of a computer program. Throughout this document a notation is used, where the MSB has the index 0.
With respect to timing, Carry-Select Adder structures are among the fastest. An example of a Carry-Select Adder structure 10 is shown in FIG. 9. As shown in FIG. 9, two pre-calculated sums sum0, sum1 of bit-groups, e.g. bytes 11, 11′, 11″ are provided, one sum sum1 assuming an initial carry-in of ‘1’, the other sum0 a carry-in of ‘0’, respectively. Thereby particular desired pre-calculated sums sum0, sum1 of the bytes 11, 11′, 11″ are selected at two-way multiplexers 12, 12′, 12″ by so-called Hot-Carry signals representing a so-called Hot-Carry, which is the actual carry-in to the appropriate byte 11, 11′, 11″. By controlling a multiplexer 12, 12′, 12″ the Hot-Carry signal selects the desired pre-calculated byte sum sum0 or sum1.
Gating of the multiplexer 12, 12′, 12″ retires orthogonal signal levels of the Hot-Carries. This means that to select a particular pre-calculated sum0 or sum1 of one byte 11, 11′, 11″, the multiplexer 12, 12′, 12″ requires not only the Hot-Carry signals but also second signals showing an orthogonal signal level with respect to the Hot-Carry signals. E.g. if the signal level of a Hot-Carry signal is high (i.e. ‘1’), a second signal having a low signal level (i.e. ‘0’) is required.
The Hot-Carry signals are provided by a carry generation network, also called Hot-Carry network, 13. The Hot-Carry network 13 comprises a carry lookahead tree working with a serial combination of generate- and propagate-based Boolean operations.
According to the state of the art, an orthogonal signal level of Hot-Carry signals is generated by an inverter stage 14, 14′, 14″. This inverter stage 14, 14′, 14″ is an additional logical level in the most timing critical Hot-Carry path. Furthermore this inverter stage 14, 14′, 14″ adds additional load and delay to the most timing critical Hot-Carry signal and increases the Fan-Out of the Hot-Carry.
It is therefore desirable, if the inverter stage can be completely avoided.